#ifndef MNOQUE_H_
#define MNOQUE_H_

#include <algorithm>
#include <functional>
#include <utility>
#include <vector>

namespace lxj
{
// 滑动窗口最大值（单调队列经典用法模版）
// 给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧
// 你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
// 返回 滑动窗口中的最大值 。
// 测试链接 : https://leetcode.cn/problems/sliding-window-maximum/
inline std::vector<int> maxSlidingWindow(std::vector<int>& nums, int k)
{
    constexpr int MAXN        = 100001;
    static int    deque[MAXN] = {};
    int           h = 0, t = 0, n = nums.size();
    for (int i = 0; i < k - 1; i++) {
        while (h < t && nums[deque[t - 1]] <= nums[i]) {
            t--;
        }
        deque[t++] = i;
    }

    int              m = n - k + 1;
    std::vector<int> ans(m);
    for (int l = 0, r = k - 1; l < m; l++, r++) {
        while (h < t && nums[deque[t - 1]] <= nums[r]) {
            t--;
        }
        deque[t++] = r;
        ans[l]     = nums[deque[h]];
        if (deque[h] == l) {
            h++;
        }
    }
    return ans;
}

// 绝对差不超过限制的最长连续子数组
// 给你一个整数数组 nums ，和一个表示限制的整数 limit
// 请你返回最长连续子数组的长度
// 该子数组中的任意两个元素之间的绝对差必须小于或者等于 limit
// 如果不存在满足条件的子数组，则返回 0
// 测试链接 :
// https://leetcode.cn/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/
class LongestSubarrayAbsoluteLimit {
    inline constexpr static int MAXN           = 100001;
    inline static int           maxDeque[MAXN] = {};
    inline static int           minDeque[MAXN] = {};
    int                         maxh, maxt, minh, mint;
    std::vector<int>            arr;

    inline bool ok(int limit, int number)
    {
        int max = maxh < maxt ? std::max(arr[maxDeque[maxh]], number) : number;
        int min = minh < mint ? std::min(arr[minDeque[minh]], number) : number;
        return max - min <= limit;
    }

    inline void push(int index)
    {
        while (maxh < maxt && arr[maxDeque[maxt - 1]] <= arr[index]) {
            maxt--;
        }
        maxDeque[maxt++] = index;
        while (minh < mint && arr[minDeque[mint - 1]] >= arr[index]) {
            mint--;
        }
        minDeque[mint++] = index;
    }

    inline void pop(int index)
    {
        if (maxh < maxt && maxDeque[maxh] == index) {
            maxh++;
        }
        if (minh < mint && minDeque[minh] == index) {
            minh++;
        }
    }

public:
    inline int longestSubarray(std::vector<int>& nums, int limit)
    {
        maxh = maxt = minh = mint = 0;
        arr                       = nums;
        int n                     = nums.size();
        int ans                   = 0;
        for (int l = 0, r = 0; l < n; l++) {
            while (r < n && ok(limit, nums[r])) {
                push(r++);
            }
            ans = std::max(ans, r - l);
            pop(l);
        }
        return ans;
    }
};

// 接取落水的最小花盆
// 老板需要你帮忙浇花。给出 N 滴水的坐标，y 表示水滴的高度，x 表示它下落到 x 轴的位置
// 每滴水以每秒1个单位长度的速度下落。你需要把花盆放在 x 轴上的某个位置
// 使得从被花盆接着的第 1 滴水开始，到被花盆接着的最后 1 滴水结束，之间的时间差至少为 D
// 我们认为，只要水滴落到 x 轴上，与花盆的边沿对齐，就认为被接住
// 给出 N 滴水的坐标和 D 的大小，请算出最小的花盆的宽度 W
// 测试链接 : https://www.luogu.com.cn/problem/P2698
class FallingWaterSmallestFlowerPot {
    inline constexpr static int      MAXN           = 100005;
    inline static int                maxDeque[MAXN] = {};
    inline static int                minDeque[MAXN] = {};
    int                              maxh, maxt, minh, mint;
    std::vector<std::pair<int, int>> arr;

    inline bool ok(int limit)
    {
        int max = maxh < maxt ? arr[maxDeque[maxh]].second : 0;
        int min = minh < mint ? arr[minDeque[minh]].second : 0;
        return max - min >= limit;
    }

    inline void push(int index)
    {
        while (maxh < maxt && arr[maxDeque[maxt - 1]].second <= arr[index].second) {
            maxt--;
        }
        maxDeque[maxt++] = index;
        while (minh < mint && arr[minDeque[mint - 1]].second >= arr[index].second) {
            mint--;
        }
        minDeque[mint++] = index;
    }

    inline void pop(int index)
    {
        while (maxh < maxt && maxDeque[maxh] == index) {
            maxh++;
        }
        while (minh < mint && minDeque[minh] == index) {
            minh++;
        }
    }

public:
    inline int sfp(const std::vector<std::pair<int, int>> waterPos, int limit)
    {
        arr = waterPos;
        std::sort(arr.begin(), arr.end(), std::less<std::pair<int, int>>());
        int n = arr.size();
        maxh = maxt = minh = mint = 0;

        int ans = ~(1 << 31);
        for (int l = 0, r = 0; l < n; l++) {
            while (!ok(limit) && r < n) {
                push(r++);
            }
            if (ok(limit)) {
                ans = std::min(ans, arr[r - 1].first - arr[l].first);
            }
            pop(l);
        }
        return ans;
    }
};
}   // namespace lxj

#endif